import java.util.Arrays;
import java.util.PriorityQueue;

public class 水位上升的泳池中游泳 {
    public static int[] move = {1,0,-1,0,1};
    public int swimInWater(int[][] grid) {
        // 构造一下距离和 vis
        int n = grid.length;
        int m = grid[0].length;
        int[][] distance = new int[n][m];
        for (int[] a : distance){
            Arrays.fill(a,Integer.MAX_VALUE);
        }
        boolean[][] vis = new boolean[n][m];
        distance[0][0] = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[2]-b[2]);
        heap.offer(new int[]{0,0,grid[0][0]});
        while (!heap.isEmpty()) {
            int[] t = heap.poll();
            int a = t[0]; // i
            int b = t[1]; // j
            int c = t[2]; // 到 b 点所需要的代价
            if (a == n - 1 && b== m - 1) {
                return c;
            }
            if (vis[a][b]) {
                continue;
            }
            vis[a][b] = true;
            for (int i = 0; i < 4; i++) {
                int x = a + move[i];
                int y = b + move[i + 1];
                if (x >= 0 && y >= 0 && x < n && y < m && !vis[x][y]) {
                    int nc = Math.max(grid[x][y],c);
                    if(nc < distance[x][y]) {
                        distance[x][y] = nc;
                        heap.offer(new int[]{x,y,nc});
                    }
                }
            }
        }
        return -1;
    }
}
